#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <unistd.h>
#include "mpi.h"
#include "quicksort.h"

#define MAX_BUFFER 1000000

// Estrutura de uma árvore binária
typedef struct stt_tree {
    int *local;
    struct stt_tree *filho_esq;
    struct stt_tree *filho_dir;
} arvore_b;


// Variáveis globais
MPI_Status status;
int size, rank; // Controle do MPI
int k;          // Dimensão do problema
int iter;       // Quantidade de iterações
int n_nivel;    // Nível do problema quase sequencial
int **repr;     // Para armazenar a representação da árvore
int tam_repr;

short *send_buffer;
int count_buffer = 0;


// Função principal que constrói uma KD Tree
void kdtree(int **p, int profundidade, int n_pontos, int indice, int iter_local) {
    
    int i;
    
    if (!p[0])
        return;
    
    // Selecionando o eixo baseado na profundade tal que o eixo circule em
    // torno de todos os valores válidos.
    int eixo;
    eixo = (profundidade % k);
    
    // Ordena a lista de pontos
    quick_sort(p, 0, n_pontos-1, eixo);
    
    // Escolhe o ponto medio como o elemento pivo
    int meio;
    meio = n_pontos / 2;
    
    int caminho;    // Para determinar o caminho da recursao ate o nivel correto
    int casa;       // Casa decimal usada na formula para calcular o caminho
    casa = pow(2, (n_nivel-1-profundidade));
    caminho = rank & casa;
    
    // Determina pontos que vão à direita e à esquerda da árvore
    int **pontos_esq = NULL;
    int **pontos_dir = NULL;
    
    // Recupera o valor mediano para inserir no nó atual
    int *valor_meio = malloc(sizeof(int) * k);
    memcpy(valor_meio, p[meio], sizeof(int) * k);
    
    // Inserindo dados nas representações da árvore
    
    
        if (rank != 0) {
            if (count_buffer+k+2 > MAX_BUFFER) {
                if (iter_local > iter-2) {
                    MPI_Send(&count_buffer, 1, MPI_INT, 0, 1, MPI_COMM_WORLD);
                    MPI_Send(send_buffer, count_buffer, MPI_SHORT, 0, 2, MPI_COMM_WORLD);
                    memset(send_buffer, 0, sizeof(short) * MAX_BUFFER);
                }
                count_buffer = 0;
            }
            for (i=0; i<k; i++) {
                send_buffer[count_buffer] = (short) valor_meio[i];
                count_buffer++;
            }
            
            send_buffer[count_buffer] = ((short) indice) & 0x0000FFFF;
            count_buffer++;
            send_buffer[count_buffer] = (short) (indice >> 16);
            count_buffer++;
            
        } else {
            repr[indice] = malloc(sizeof(int*) * k);
            memcpy(repr[indice], valor_meio, sizeof(int) * k);
        }
    

    
    // Determina se terá recursão à esquerda
    if (!caminho || profundidade >= n_nivel) {
        // Gerando uma nova lista de pontos
        pontos_esq = malloc(sizeof(int*) * meio+1);
        i = 0;
        while (i < meio) {
            pontos_esq[i] = malloc(sizeof(int) * k);
            memcpy(pontos_esq[i], p[i], sizeof(int) * k);
            i++;
        }
        pontos_esq[i] = NULL;
    }
    
    // Determina se terá recursão à direita
    if (caminho || profundidade >= n_nivel) {
        pontos_dir = malloc(sizeof(int*) * (n_pontos-meio+1));
        i = 0;
        while (i < n_pontos-meio-1) {
            pontos_dir[i] = malloc(sizeof(int*) * k);
            memcpy(pontos_dir[i], p[i+meio+1], sizeof(int) * k);
            i++;
        }
        pontos_dir[i] = NULL;
    }
    
    // Desalocando memória referente aos pontos
    if (profundidade != 0) {
        for (i=0; i<=n_pontos-1; i++)
            free(p[i]);
        free(p);
    }
    
    // Chamando recursão para esquerda
    if (!caminho || profundidade >= n_nivel)
        kdtree(pontos_esq, profundidade+1, meio, 2*indice, iter_local);
    // Chamando recursão para esquerda
    if (caminho || profundidade >= n_nivel)
        kdtree(pontos_dir, profundidade+1, n_pontos-meio-1, 2*indice+1, iter_local);
}


arvore_b* monta() {
    int i;
    arvore_b** resposta;
    resposta = (arvore_b**) malloc(sizeof(arvore_b*) * tam_repr);
    for (i=1; i<=tam_repr; i++) {
        resposta[i] = (arvore_b*) malloc(sizeof(arvore_b));
        resposta[i]->local = repr[i];
    }
    for (i=1; i<=tam_repr/2; i++) {
        resposta[i]->filho_esq = resposta[i*2];
        resposta[i]->filho_dir = resposta[i*2+1];
    }
    return resposta[1];
}


int main(int argc, char *argv[]) {
    // Inicia o MPI
    MPI_Init(&argc,&argv);
    MPI_Comm_size(MPI_COMM_WORLD,&size);
    MPI_Comm_rank(MPI_COMM_WORLD,&rank);
    
    k = atoi(argv[1]);              // Tamanho da dimensão
    iter = atoi(argv[2]);           // Iterações
    int n_pontos = atoi(argv[3]);   // Número de pontos retirados do arquivo
    
    // Calcula o tamanho do caminho de cada nó até executar independentemente
    int q = size;
    n_nivel = 0;
    while (!(q & 1)) {
        n_nivel++;
        q >>= 1;
    }
    
    // Alocação do conjunto de representação com tamanho de árvore completa
    if (rank == 0) {
        float res = log(n_pontos) / log(2);
        if (res == (int)res)
            tam_repr = (1 << (((int) res )));
        else
            tam_repr = (1 << (((int) res ) + 1));
        repr = malloc(sizeof(int*) * tam_repr);
        memset(repr, 0, sizeof(int*) * tam_repr);
    }
    
    // Ranks que não forem 0, alocam um vetor de pontos para enviar no final
    if (rank != 0)
        send_buffer = malloc(sizeof(short) * MAX_BUFFER);
    
    
    int ponto[k], i, j, w;
    
    // Lendo cada linha da entrada e atribuindo os valores
    int **pontos;
    pontos = malloc(sizeof(int*) * n_pontos + 1);

    // Lendo os pontos
    srand(10);
    for (i=0; i<n_pontos; i++) {
        for(j=0; j < k-1; j++)
            //res = fscanf(arquivo, "%d ", &ponto[j]);
            ponto[j] = rand() % 1000;
        //res = fscanf(arquivo, "%d", &ponto[j]);
        ponto[j] = rand() % 1000;
        pontos[i] = malloc(sizeof(int) * k);
        for (j=0; j<k; j++)
            pontos[i][j] = ponto[j];
    }
    pontos[i] = NULL;
    
    for (w=0; w<=iter; w++) {
        
        if (w % size == rank) {
            
            printf("Iteração %d do processo %d\n", w, rank);
            // Inicia programa computação do problema
            count_buffer = 0;
            kdtree(pontos, 0, n_pontos, 1, w);
            
            if (w < iter && rank == 0) {
                for (i=0; i<=tam_repr; i++)
                    free(repr[i]);
            }
        }
    }
    
    if (rank != 0) {
        MPI_Send(&count_buffer, 1, MPI_INT, 0, 1, MPI_COMM_WORLD);
        MPI_Send(send_buffer, count_buffer, MPI_SHORT, 0, 2, MPI_COMM_WORLD);
        int stop = -1;
        MPI_Send(&stop, 1, MPI_INT, 0, 1, MPI_COMM_WORLD);
    }
    else {
        // Recebe dados de todos os outros processos 
        if (rank == 0 && size > 1) {
            for (i=1; i<size; i++) {
                while (1) {
                    int tam_buffer;
                    MPI_Recv(&tam_buffer, 1, MPI_INT, i, 1, MPI_COMM_WORLD, &status);
                    
                    if (tam_buffer != -1) {
                        //printf("Recebeu mensagem com buffer = %d\n", tam_buffer);
                        short buffer_local[tam_buffer];
                        MPI_Recv(buffer_local, tam_buffer, MPI_SHORT, i, 2, MPI_COMM_WORLD, &status);
                        for (j=0; j<tam_buffer; j+=k+2) {
                            int indice = (((int) buffer_local[j+3]) & 0x0000FFFF) |  ( (int) buffer_local[j+4] << 16);
                            repr[indice] = malloc(sizeof(int*) * k);
                                for (w=0; w<k; w++)
                                    repr[indice][w] = (int) buffer_local[j+w];
                        }
                    } else break;
                }
            }
        }
        // Monta a árvore através da representação
        arvore_b *tree;
        tree = monta();
        
        printf("(%d, %d, %d)\n", tree->local[0], tree->local[1], tree->local[2]);
        printf("(%d, %d, %d)\n", tree->filho_esq->local[0], tree->filho_esq->local[1], tree->filho_esq->local[2]);
        printf("(%d, %d, %d)\n", tree->filho_dir->local[0], tree->filho_dir->local[1], tree->filho_dir->local[2]);
    }
    
    MPI_Finalize(); // Termina o processo gerado pelo MPI
    return 0;
}
